//
// Created by tzq on 2022/6/1.
//
#include <stdio.h>
#include "reverse.h"


//iteration_reverse 迭代反转链表
link *iteration_reverse(link *head) {
    //如果头指针为空以及只有一个链表节点的情况下，直接返回不需要反转
    if (head == NULL || head->next == NULL) {
        return head;
    }

    //借助三个指针 beg mid end 不断向后移动，直到end 为 NULL
    link *beg = NULL;
    link *mid = head;
    link *end = head->next;

    while (1) {

        mid->next = beg;
        if (end == NULL) {
            break;
        }

        beg = mid;
        mid = end;
        end = mid->next;
    }

    head = mid;
    return head;
}


//recursive_reverse 递归法反转链表
link *recursive_reverse(link *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    } else {
        link *newHead = recursive_reverse(head->next);
        head->next->next = head;
        head->next = NULL;
        return newHead;
    }


}

//head_reverse 头插法反转链表
link *head_reverse(link *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    //声明一个新链表
    link *new_head = NULL;
    link *temp = NULL;
    while (head != NULL) {
        temp = head;

        head = head->next;
        temp->next = new_head;
        new_head = temp;
    }

    return new_head;
}

//local_reverse 就地逆置法反转链表
link *local_reverse(link *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    link *beg = head;
    link *end = head->next;

    while (end != NULL) {
        //摘除节点
        beg->next = end->next;
        end->next = head;
        head = end;
        end = beg->next;
    }

    return head;
}

